
class Solution {
    public:
        int waysToStep(int n) {
            //动态规划问题dp【i】表示以i为结尾，一共有多少种方式
            //状态转移方程dp[i] = dp[i-3]+dp[i-2]+dp[i-1]
            //初始化dp[1] dp[2] dp[3]
            //从左向右填表
            //直接返回dp[n]即可
            if(n == 1) return 1;
            if(n == 2) return 2;
            if(n == 3 ) return 4;
            vector<long long> dp(n+1);
            dp[1]=1,dp[2]=2,dp[3]=4;
            for(long long i = 4 ; i <= n ; i++){
                dp[i] = (dp[i-3]+dp[i-2]+dp[i-1])%1000000007;
            }
            return dp[n];
        }
    };